/*
 * @lc app=leetcode.cn id=382 lang=typescript
 *
 * [382] 链表随机节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
class Solution {
  head: ListNode;
  constructor(head: ListNode | null) {
    this.head = head;
  }

  getRandom(): number {
    let node = this.head;
    let ans: number;
    let i = 0;
    while (node) {
      i++;
      // 随机抽样
      const rand = Math.ceil(Math.random() * i);
      if (rand === i) {
        ans = node.val;
      }
      node = node.next;
    }

    return ans;
  }
}

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(head)
 * var param_1 = obj.getRandom()
 */
// @lc code=end
